1. Field of the Invention
This invention relates to digital maps of the type for displaying road or pathway information, and more particularly toward a method for verifying and updating information contained in a digital map using probe data.
2. Related Art
Personal navigation devices like that shown for example in FIG. 1 utilize digital maps combined with accurate positioning data from GPS or other data streams. These devices have been developed for many applications, such as navigation assistance for automobile drivers. The effectiveness of these navigation systems is inherently dependent upon the accuracy of the information provided to it in the form of digital maps, stored in its memory or otherwise accessed through a suitable database connection such as wireless signal, cable, telephone line, etc.
Typically, the navigation system 10 (FIG. 1) includes a display screen 12 that portrays a portion of a stored digital map as a network of roads 14. A traveler having access to a GPS-enabled navigation device 10 may then be generally located on the digital map close to or with regard to a particular road 14 or segment thereof. Some GPS-enabled navigation devices 10, like several models manufactured by TomTom NV (www.tomtom.com), may also be configured as probes to passively generate probe measurement points at regular intervals. Such probe traces comprise a sequence of discrete geo-coded positions recorded at intervals of, for example, five seconds. Of course, other suitable devices may be used to generate probe measurement points including, for example, handheld devices, mobile phones, PDAs, and the like. Thus, probe data may be described as a set of information about movement of a vehicle (or a person carrying a probe) which contains time-stamped geographic locations (xyz coordinates) and possibly also metadata (vehicle speed, receiver type, vehicle type, etc.).
It is known to take collections of probe measurements for the purpose of incrementally creating and/or updating digital maps. The probe measurements can be transmitted either on-the-fly or subsequently to a collection service or other map data analysis service via wireless (e.g., cellular) transmission, via internet uploads, or by other convenient methods. Internet uploads may be synchronized to occur in conjunction with digital map upgrades which navigation device users might obtain as part of a service. From the collection of probe measurements, road geometries can be inferred and other features and attributes derived by appropriate analytical methods.
A typical collection of probe measurements collected from a plurality of probes traversing a particular section of a digital map over a period of time may contain billions of discrete data points, each geo-coded and time stamped. Probe traces collected over time can be grouped according to those which match to a common area of the digital map and then overlaid for interpretation by map database editors. These editors use various mathematic and statistical techniques to determine or infer road geometries, compute speed profiles, acceleration profiles, direction of travel, altitude, detect changes in road networks, to compare two road networks, and many other specifications.
As suggested previously, the effectiveness of a personal navigation device 10 depends upon the accuracy of the information contained in the digital map. Digital map providers continuously strive to improve and update their maps. Inaccurate data, for example, may be unsuitable to compute optimal routes in response to a navigation query, or to provide other reliable information to a traveler. Inaccurate or incomplete information contained in a digital map can result in poor or erroneous navigation instructions and lead to undesirable navigation decisions.
Navigation decisions almost always take into account natural features of the landscape, which often present barriers to travel. For example, an inland water barrier, such as a river, canal, drainage, marsh, lake or bay, represents a constraint to vehicular travel, as well as to pedestrian and bicycle travel. Typically, an inland water barrier may be crossed only with the aid of a ferry, bridge or tunnel. In mountainous terrain, tunnels are sometimes cut through a mountain and bridges are sometimes placed across deep valleys and gorges. The existence or nonexistence of a bridge, ferry or tunnel constitutes an important detail to be recorded in a digital map. Likewise, the average speed over which historically measured vehicular traffic crosses a barrier is also an important detail for inclusion in digital maps.
Until now, there is no effective method by which to analyze probe measurements to determine whether a particular inland barrier crossing comprises a bridge or a ferry or a tunnel. Therefore, there is a need in the art for an improved method for efficiently analyzing probe measurements for the benefit of database editors to validate and/or determine the specification for an inland barrier crossing, i.e., either a bridge or a ferry, or perhaps a tunnel.